home *** CD-ROM | disk | FTP | other *** search
/ AmigActive 10 / AACD 10.iso / AACD / Programming / AmigaTalk / examples / TuringMachineSim.st < prev   
Text File  |  1998-09-30  |  3KB  |  134 lines
  1. "
  2.    Turing machine simulator contributed by Jan Gray,
  3.    the University of Waterloo
  4. "
  5. Class Main
  6. [
  7.   main | tm |
  8.     tm <- TuringMachine new initialize.
  9.  
  10.     tm delta state: 0 input: $# nextState: 1 output: $L.
  11.     tm delta state: 1 input: $I nextState: 1 output: $i.
  12.     tm delta state: 1 input: $i nextState: 1 output: $L.
  13.     tm delta state: 1 input: $# nextState: 2 output: $R.
  14.     tm delta state: 2 input: $i nextState: 2 output: $R.
  15.     tm delta state: 2 input: $# nextState: 'halt' output: $#.
  16.     tm tape: 'IIIIII'.
  17.     tm delta print.
  18.     tm run
  19. ]
  20.  
  21. Class TuringMachine
  22. |  tape      "Infinite tape"
  23.    state      "Current state, TM continues if state is a number"
  24.    delta      "A TransitionTable, which for each (state, input)
  25.                gives (next state, output)"
  26.    tapeMoves  "A Dictionary which maps L and R into [tape left]
  27.                and [tape right]"
  28. |
  29. [
  30.   initialize
  31.     tapeMoves <- Dictionary new.
  32.     tapeMoves at: $L put: [tape left].
  33.     tapeMoves at: $R put: [tape right].
  34.  
  35.     delta <- TransitionTable new.
  36.  
  37.     self tape: ''.
  38.     self state: 0
  39. |
  40.   tape: aString
  41.     tape <- Tape new with: aString
  42. |
  43.   state: aState
  44.     state <- aState
  45. |
  46.   delta
  47.     ^ delta
  48. |
  49.   step | next |
  50.     next  <- delta atState: state input: tape read.
  51.     state <- next state.
  52.  
  53.     (state isKindOf: Number)
  54.        ifTrue: [(tapeMoves includesKey: next symbol)
  55.                  ifTrue:   [(tapeMoves at: next symbol) value]
  56.                  ifFalse: [tape write: next symbol]
  57.                ]
  58. |
  59.   run
  60.     state <- 0.
  61.     self print.
  62.     [state isKindOf: Number] whileTrue: [self step print]
  63. |
  64.   printString
  65.     ^ 'State ', state printString, ', Tape ', tape printString
  66. ]
  67.  
  68. Class Pair :Magnitude
  69. | state symbol |
  70. [
  71.   state: aState symbol: aSymbol
  72.     state  <- aState.
  73.     symbol <- aSymbol
  74. |
  75.   state
  76.     ^ state
  77. |
  78.   symbol
  79.     ^ symbol
  80. |
  81.   < aPair
  82.     ^ state < aPair state or: [state = aPair state 
  83.                                 and: [symbol < aPair symbol]
  84.                               ]
  85. |
  86.   printString
  87.     ^ state printString, '   ', symbol printString
  88. ]
  89.  
  90. Class TransitionTable :Dictionary
  91. [
  92.   state: aState input: in nextState: nextState output: out
  93.    self at: (Pair new state: aState symbol: in)
  94.        put: (Pair new state: nextState symbol: out).
  95.    ^ nil
  96. |
  97.   atState: aState input: in
  98.     ^ self at: (Pair new state: aState symbol: in)
  99.          ifAbsent: [^ Pair new state: 'hung' symbol: nil].
  100. |
  101.   print
  102.     'State   Read   Next   Write' print.
  103.     self binaryDo: [:x :y | (x printString , '   ', y printString) print]
  104. ]
  105.  
  106. Class Tape :Object
  107. | tape position |
  108. [
  109.   with: aString
  110.     tape     <- '#', aString, '#'.
  111.     position <- tape size
  112. |
  113.   read
  114.     ^ tape at: position
  115. |
  116.   write: aChar
  117.     tape at: position put: aChar.
  118. |
  119.   left
  120.     (position > 1)
  121.        ifTrue: [position <- position - 1]
  122. |
  123.   right
  124.     (position = tape size)
  125.        ifTrue: [tape <- tape, '#'].
  126.  
  127.     position <- position + 1
  128. |
  129.   printString
  130.     ^ (tape copyFrom: 1 to: position - 1), '{',
  131.        ((tape at: position) asString), '}',
  132.        (tape copyFrom: position + 1 to: tape size)
  133. ]
  134.